package 寒假刷题;

import java.util.ArrayList;
import java.util.List;

public class 字典树排序 {
//    迭代解法，不好记
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0,j=1; i < n; i++) {
            list.add(j);
            if (j*10<=n){
                j*=10;
            }
            else{
                while (j%10==9 || j+1>n){
                    j/=10;
                }
                j++;
            }
        }
        return list;
    }
    List<Integer> list = new ArrayList<>();
    public List<Integer> lexicalOrder2(int n) {
        for (int i = 1; i <=9 ; i++) {
            dfs(i,n);
        }
        return list;
    }

    private void dfs(int cur, int n) {
        if (cur>n)
            return;
        list.add(cur);
        for (int i = 0; i <= 9 ; i++) {
            dfs(cur*10+i,n);
        }
    }
}
